package com.lh.nk;

/**
 * @author: linghao
 * @since: 2023/1/19
 * 描述
 * 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
 * 处理回文字符串的算法：Manacher（俗称“马拉车”）
 * BM65 最长公共子序列(二)
 *
 * BM66.最长公共子串
 *
 * BM71.最长上升子序列(一)
 *
 * BM75 编辑距离(一)
 *
 * BM76 正则表达式匹配
 *
 * BM77 最长的括号子串
 */
public class 最长回文子串NC17 {

    public static void main(String[] args) {
//        System.out.println(getLongestPalindrome("civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"));
        System.out.println(getLongestPalindrome("abc1234321ab"));
    }


//    public static int getLongestPalindrome (String A){
//
//    }


    /**
     * 暴力解法，双重循环遍历所有子串后判断是否回文
     * @param A
     * @return
     */
    public static int getLongestPalindrome (String A) {
        // write code here
        int max = 0;
        for(int i=0;i<A.length();i++){
            for(int j=i+1;j<=A.length();j++){   //j<=A.length() 因为A.substring(i,j) 的j需要取值
                if(isPalindrome(A.substring(i,j),j-i)){
                    if(j-i>max){
                        max = j-i;
                    }
                }
            }
        }
        return max;
    }

    private static boolean isPalindrome(String temp,int n) {
        int k = n/2;
        for(int i=0;i<k;i++){
            if(temp.charAt(i) != temp.charAt(n-i-1)){
                return false;
            }
        }
        return true;
    }
}
